The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols. Elements in the network are typically identifiable by a unique internet protocol (IP) address.
One routing protocol used, for example, in the internet is Border Gateway Protocol (BGP). BGP is used to route data between autonomous systems (AS) comprising networks under a common administrator and sharing a common routing policy. BGP routers exchange full routing information during a connection session for example using Transmission Control Protocol (TCP) allowing inter-autonomous system routing. The information exchanged includes various attributes including a next-hop attribute. For example where a BGP router advertises a connection to a network, for example in a form of an IP address prefix, the next-hop attribute comprises the IP address used to reach the BGP router.
Within each AS the routing protocol typically comprises an interior gateway protocol (IGP) for example a link state protocol such as open shortest path first (OSPF) or intermediate system-intermediate system (IS-IS).
The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node the node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.
When IS-IS is deployed as IGP in an AS or routing domain it can be configured using separate areas, for example for scaling purposes. In that case a two-level routing hierarchy is used all routers common to an area comprising level 1 routers. The areas are connected via a backbone of level 2 routers. As a result routing within the routing domain is carried out between level 1 routers in a given area and through the level 2 backbone between the areas. Accordingly when a link to a neighboring network node is advertised in an LSP, for example in the form of a prefix originated by a router in a level 1 area, this is “propagated” from level 1 to level 2 and then via the backbone to other level 2 routers. The route is then “leaked” down from the level 2 routers to level 1 routers in other areas. Route propagation and leaking is handled by routers participating in both levels, termed level 1-2 routers. When a prefix is propagated from level 1 to level 2 (or leaked from level 2 to level 1), a restricted amount of information is carried over including the advertised prefix and any associated metric (for example the cost of the link).
When OSPF is deployed as IGP then a similar structure is adopted with slightly different terminology. In particular the backbone is designated area zero and this connects multiple numbered areas via area border routers (ABR).
It is desirable to monitor the flow of traffic on the Internet between network ingress and network egress points for example for the purposes of network wide capacity planning, traffic engineering and destination sensitive billing all of which require a network-wide view of the traffic crossing the network. In particular, for each entry point of the network it is necessary to know where the traffic will exit the network and this information can be stored in a core traffic matrix (TM). One known traffic monitoring system is NetFlow provided by Cisco Systems, Inc, San Jose, Calif. According to this system traffic is classified at the entry point of the network and flow records are exported to a NetFlow collector where an aggregation at the core traffic matrix level is carried out based on additional information available from router configurations and routing tables. NetFlow further provides aggregation based on the BGP next-hop attribute allowing creation of the core TM for all BGP routes, where the egress router of a route is identified using the next-hop attribute.
It is also desirable to produce a core TM directly in a router for link-state IGP prefixes. At present, however, when a routing update crosses an ABR (OSPF) or a level 1-2 router (IS-IS), the information about the originator of the prefix is lost so that the core TM cannot be completed at routers in other areas than the originating router.
In “A Distributed Approach to Measure IP Traffic Matrices” of Papagiannaki et al which is available at the time of writing on the file “Taft-IMC04.pdf” in the directory “nina/Publications/” of the domain “http://berkeley.intel-research.net/” a monitoring approach is described which relies on additional topology information and requiring exporting flow records and using routing tables and router configuration.